/**
 * Created by L.jp
 * Description:给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成
 * 示例 1:
 * 输入: "abab"
 * 输出: True
 * 解释: 可由子字符串 "ab" 重复两次构成。
 * 示例 2:
 * 输入: "aba"
 * 输出: False
 * 示例 3:
 * 输入: "abcabcabcabc"
 * 输出: True
 * 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
 * User: 86189
 * Date: 2021-12-11
 * Time: 22:38
 */
//判断一个字符串是不是由多个子串重复构成，说明前提肯定是要有子串，那么这个就是前面kmp算法的变形，这次不需要求子串出现的位置，而是判断有没有多个子串构成主串
//原理：
//需要先构造next数组求得每个位置前缀后缀表的长度（也就是我们所说的匹配失败时需要回退的位置），
// 那么next数组最后一个位置next[s.length-1]再+1就是最长相同前后缀的长度------maxLen=next[len-1]+1
// 如果这个数值等于0说明没有子串，就不存在重复这一说，返回false----if(maxLen==0) return false
// 那么每一个重复子串的长度的计算就是用主串的长度减去最长相同前后缀的长度-----len-maxLen
// 如果用主串长度模上重复子串的长度等于0，那么就表示可以由多个重复子串构成，返回true;-----if(len%(len-maxLen))==0  return true;
public class Solution {
    /**
     * @param s: 构造next数组时，这里的主串就当做子串
     * [s]
     * @return int
     * @description TODO  构造next数组
     */
    public static int[] getNext(String s){
        int len=s.length();
        int[] next=new int[len+1];
        next[0]=-1;
        next[1]=0;
        int j=2;
        int k=0;
        while(j<len){
            if(k==-1 || s.charAt(j-1)==s.charAt(k)){
                next[j]=k+1;
                j++;
                k++;
            }else{
                k=next[k];
            }
        }
        return next;
    }
    /**
     * @param s:
     * [s]
     * @return boolean
     * @description TODO
     */
    public static boolean repeatedSubstringPattern(String s) {
        int[] next=getNext(s);
        int len=s.length();
        int maxLen=next[len-1]+1;
        if(maxLen==0){
            return false;
        }
        //这个方法最后还要加上一个判断条件，如果一个主串可以由多个子串构成，那么对应的位置的字符一定是一样的，不一样就会直接返回false
        if(s.charAt(len-1)!=s.charAt(len-maxLen-1)){
            return false;
        }
        return s.length()%(s.length()-maxLen)==0;
    }

    public static void main(String[] args) {
        String s="abcabc";
        System.out.println(repeatedSubstringPattern(s));
    }
}
